﻿#pragma once

#include<iostream>
using namespace std;
#include<vector>
#include<time.h>
#include<random>
#include<chrono>



struct SkiplistNode
{
    int _val;
    vector<SkiplistNode*> _nextV;

    SkiplistNode(int val,int level)
        :_val(val)
        ,_nextV(level,nullptr)
    {}
};

//跳表关键：
// 比他大 往右走 
// 比他小 往下走

class Skiplist 
{
    typedef SkiplistNode Node;
public:
    Skiplist() 
    {
        srand(time(0));
        _head = new SkiplistNode(-1, 1);
    }

    bool search(int target) 
    {
        Node* cur = _head;
        int level = cur->_nextV.size() - 1;
        while (level >= 0)
        {
            if (cur->_nextV[level] && target > cur->_nextV[level]->_val)
            {
                cur = cur->_nextV[level];
            }
            else if (cur->_nextV[level] == nullptr || target < cur->_nextV[level]->_val)
            {
                --level;
            }
            else
            {
                return true;
            }
        }
        return false;
    }

    vector<Node*> FindPrevNode(int num)
    {
        Node* cur = _head;
        int level = cur->_nextV.size() - 1;
        vector<Node*> prevV(level + 1, _head);

        while (level >= 0)
        {
            if (cur->_nextV[level] && num > cur->_nextV[level]->_val)
            {
                cur = cur->_nextV[level];
            }
            else if (cur->_nextV[level] == nullptr || num <= cur->_nextV[level]->_val)
            {
                prevV[level] = cur;
                --level;
            }
        }
        return prevV;
    }

    //插入节点的关键是找到这个位置的每一层前一个结点
    void add(int num) 
    {
        vector<Node*> prevV = FindPrevNode(num);
        int n = RandomLevel();
        Node* newnode = new Node(num, n);
        if (_head->_nextV.size() < n)
        {
            _head->_nextV.resize(n,nullptr);
            prevV.resize(n, _head);
        }

        for (size_t i = 0; i < n; i++)
        {
            newnode->_nextV[i] = prevV[i]->_nextV[i];
            prevV[i]->_nextV[i] = newnode;
        }
    }

    bool erase(int num) 
    {
        vector<Node*> prevV = FindPrevNode(num);
        if (prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num)
        {
            return false;
        }
        else
        {
            Node* del = prevV[0]->_nextV[0];
            for (size_t i = 0; i < del->_nextV.size(); i++)
            {
                prevV[i]->_nextV[i] = del->_nextV[i];
            }
            delete del;

            int i = _head->_nextV.size() - 1;
            while (i >= 0)
            {
                if (_head->_nextV[i] == nullptr)
                {
                    --i;
                }
                else
                {
                    break;
                }
            }
            _head->_nextV.resize(i + 1);

            return true;
        }

    }

    int  RandomLevel()
    {
        int level = 1;
        while (rand() < RAND_MAX * _p && level < _maxlevel)
        {
            ++level;
        }
        return level;
    }

    void Print()
    {
       /* int level = _head->_nextV.size();
        for (int i = level - 1; i >= 0; --i)
        {
            Node* cur = _head;
            while (cur)
            {
                printf("%d->", cur->_val);
                cur = cur->_nextV[i];
            }
            printf("\n");
        }*/
        Node* cur = _head;
        while (cur)
        {
            printf("%2d\n", cur->_val);
            for (auto e : cur->_nextV)
            {
                printf(" ↓ ");
            }
            printf("\n");

            cur = cur->_nextV[0];
        }
    }

private:
    Node* _head ;
    size_t _maxlevel = 32;
    double _p = 0.25;
};
